package foundation.graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class SPFA {
    static int MAXN = 5001;
    static int MAXM = 10001;
    static int INF = Integer.MAX_VALUE;

    static int[] head = new int[MAXN];
    static int[] next = new int[MAXM];
    static int[] to = new int[MAXM];
    static int[] w = new int[MAXM];

    static int n;
    static int m;
    static int cur;

    // 是否在队列中
    static boolean[] st = new boolean[MAXN];
    static int[] dist = new int[MAXN];

    private static void build() {
        cur = 1;
        Arrays.fill(st, 1, n + 1, false);
        Arrays.fill(head, 1, n + 1, 0);
        Arrays.fill(dist, 1, n + 1, INF);
    }

    private static void addEdge(int u, int v, int weight) {
        // u-> v  w
        next[cur] = head[u];
        to[cur] = v;
        w[cur] = weight;
        head[u] = cur++;

    }

    private static int spfa() {
        dist[1] = 0;
        Queue<Integer> queue = new LinkedList<>();
        st[1] = true;
        queue.add(1);
        while (!queue.isEmpty()) {
            Integer t = queue.poll();
            st[t] = false;
            for (int ei = head[t]; ei > 0; ei = next[ei]) {
                int v = to[ei];
                if (dist[v] > dist[t] + w[ei]) {
                    dist[v] = dist[t] + w[ei];
                    if (!st[v]) {
                        queue.add(v);
                        st[v] = true;
                    }
                }
            }
        }
        if (dist[n] == INF) return -1;
        return dist[n];
    }

    private static void display() {
        for (int i = 1; i <= n; i++) {
            System.out.print(i + "(邻居,边权) : ");
            for (int ei = head[i]; ei > 0; ei = next[ei]) {
                System.out.print("(" + to[ei] + "," + w[ei] + ") ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        build();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            addEdge(u,v,w);
        }
        int spfa = spfa();
        System.out.println(spfa);
    }


}
